package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/reverse-nodes-in-even-length-groups">反转偶数长度组的节点(Reverse Nodes in Even Length Groups)</a>
 * <p>给你一个链表的头节点 head 。</p>
 * <p>
 * 链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。一个组的 长度 就是组中分配到的节点数目。换句话说：
 * <ui>
 * <li>节点 1 分配给第一组</li>
 * <li>节点 2 和 3 分配给第二组</li>
 * <li>节点 4、5 和 6 分配给第三组，以此类推</li>
 * </ui>
 * 注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
 * </p>
 * <p>反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [5,2,6,3,9,1,7,3,8,4]
 *      输出：[5,6,2,3,9,1,4,8,3,7]
 *      解释：
 *          - 第一组长度为 1 ，奇数，没有发生反转。
 *          - 第二组长度为 2 ，偶数，节点反转。
 *          - 第三组长度为 3 ，奇数，没有发生反转。
 *          - 最后一组长度为 4 ，偶数，节点反转。
 *
 * 示例 2：
 *      输入：head = [1,1,0,6]
 *      输出：[1,0,1,6]
 *      解释：
 *          - 第一组长度为 1 ，没有发生反转。
 *          - 第二组长度为 2 ，节点反转。
 *          - 最后一组长度为 1 ，没有发生反转。
 *
 * 示例 3：
 *      输入：head = [2,1]
 *      输出：[2,1]
 *      解释：
 *          - 第一组长度为 1 ，没有发生反转。
 *          - 最后一组长度为 1 ，没有发生反转。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>链表中节点数目范围是 [1, 10^5]</li>
 *      <li>0 <= Node.val <= 10^5</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/5 11:54
 */
public class LC2074ReverseNodesInEvenLengthGroups_M {

    static class Solution {
        public ListNode reverseEvenLengthGroups(ListNode head) {
            ListNode dummyHead = new ListNode(-1, head);
            // 用于记录上一组的尾节点
            ListNode prevGroupTailNode = dummyHead;
            // 组号，即当前组节点数量
            int groupNo = 1;
            while (prevGroupTailNode.next != null) {
                ListNode currGroupHeadNode = prevGroupTailNode.next;
                ListNode currGroupTailNode = prevGroupTailNode;
                int currGroupNodeSize = 0;
                while (currGroupNodeSize < groupNo && currGroupTailNode.next != null) {
                    ++currGroupNodeSize;
                    currGroupTailNode = currGroupTailNode.next;
                }
                // 偶数：currGroupActualNodeSize % 2 == 0
                // 小优化偶数的 最低二进制位一定为 0；那么 (currGroupNodeSize & 1) == 0 成立，说明为偶数
                if ((currGroupNodeSize & 1) == 0) {
                    // 记录下一组的头节点，并断开
                    ListNode nextGroupHead = currGroupTailNode.next;
                    currGroupTailNode.next = null;
                    // 反转链表并拼接。反转后：currGroupFirstNode 变成当前组的最后一个节点
                    prevGroupTailNode.next = reverseList(currGroupHeadNode);
                    currGroupHeadNode.next = nextGroupHead;
                    // 进行下一次循环
                    prevGroupTailNode = currGroupHeadNode;
                } else {
                    prevGroupTailNode = currGroupTailNode;
                }
                ++groupNo;
            }
            return dummyHead.next;
        }

        private ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            ListNode next;
            while (curr != null) {
                next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.reverseEvenLengthGroups(Generator.create(5, 2, 6, 3, 9, 1, 7, 3, 8, 4)));
        Printer.printListNode(solution.reverseEvenLengthGroups(Generator.create(1, 1, 0, 6)));
        Printer.printListNode(solution.reverseEvenLengthGroups(Generator.create(1, 1, 0, 6, 5, 3, 9, 7)));
    }
}